﻿using InSafetyAirServer.Database;
using InSafetyAirServer.Model;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace InSafetyAirServer.Controller
{
    public class GraphCustom : Graph<Airport, FlightSegment, Schedule>
    {
        //TODO: Daca sunt 2 edge-uri intre acelasi noduri el alege primul fara sa tina cont daca unul din ele are costul mai mic
        public Path<Airport, FlightSegment, Schedule> shortestPath(Vertex<Airport, FlightSegment, Schedule> vStart, Vertex<Airport, FlightSegment, Schedule> vEnd, string field)
        {
            int[] dist = new int[_vertices.Count];
            Path<Airport, FlightSegment, Schedule> path = new Path<Airport, FlightSegment, Schedule>();
            Vertex<Airport, FlightSegment, Schedule>[] previous = new Vertex<Airport, FlightSegment, Schedule>[_vertices.Count];
            foreach (Vertex<Airport, FlightSegment, Schedule> v in _vertices)
            {
                dist[_vertices.IndexOf(v)] = int.MaxValue;
                previous[_vertices.IndexOf(v)] = null;
            }
            dist[_vertices.IndexOf(vStart)] = 0;
            IList<Vertex<Airport, FlightSegment, Schedule>> Q = new List<Vertex<Airport, FlightSegment, Schedule>>(_vertices);
            while (Q.Count > 0)
            {
                int min = int.MaxValue;
                Vertex<Airport, FlightSegment, Schedule> u = null;
                foreach (Vertex<Airport, FlightSegment, Schedule> v in Q)
                {
                    if (dist[_vertices.IndexOf(v)] < min)
                    {
                        min = dist[_vertices.IndexOf(v)];
                        u = v;
                    }
                }
                if (u == null) break;
                if (u == vEnd)
                {
                    Vertex<Airport, FlightSegment, Schedule> prev = previous[_vertices.IndexOf(u)];
                    while (prev != null)
                    {
                        Edge<Airport, FlightSegment, Schedule> e = getEdge(prev, u);
                        if (e != null) path.AddEdge(e, field);
                        u = prev;
                        prev = previous[_vertices.IndexOf(u)];
                    }
                    path.Edges.Reverse();
                    return path;
                }
                Q.Remove(u);
                if (dist[_vertices.IndexOf(u)] == int.MaxValue)
                {
                    break;
                }


                foreach (Edge<Airport, FlightSegment, Schedule> e in u.Edges())
                {
                    Vertex<Airport, FlightSegment, Schedule> v = e.To;
                    int alt = dist[_vertices.IndexOf(u)] + (int)e.Data.price;
                    if (alt < dist[_vertices.IndexOf(v)])
                    {
                        dist[_vertices.IndexOf(v)] = alt;
                        previous[_vertices.IndexOf(v)] = u;
                    }
                }
            }
            return path;
        }

        public List<Path<Airport, FlightSegment, Schedule>> YenKSP(Vertex<Airport, FlightSegment, Schedule> vStart, Vertex<Airport, FlightSegment, Schedule> vEnd, int K, string field)
        {
            GraphCustom graph = this;
            GraphCustom graphCopy = graph;
            List<Path<Airport, FlightSegment, Schedule>> A = new List<Path<Airport, FlightSegment, Schedule>>();
            A.Add(graph.shortestPath(vStart, vEnd, field));
            List<Path<Airport, FlightSegment, Schedule>> B = new List<Path<Airport, FlightSegment, Schedule>>();
            for (int k = 1; k < K; k++)
            {
                for (int i = 0; i <= (A[k - 1].Edges.Count - 1); i++)
                {
                    Vertex<Airport, FlightSegment, Schedule> spurNode = A[k - 1].Edges[i].From;
                    Path<Airport, FlightSegment, Schedule> rootPath = A[k - 1].GetRange(0, i, field);
                    foreach (Path<Airport, FlightSegment, Schedule> p in A)
                    {
                        if (rootPath.Equals(p.GetRange(0, i, field)))
                        {
                            graph.RemoveEdge(p.Edges[i].From, p.Edges[i].To, p.Edges[i].Data);
                        }
                    }
                    Path<Airport, FlightSegment, Schedule> spurPath = graphCopy.shortestPath(spurNode, vEnd, field);
                    Path<Airport, FlightSegment, Schedule> totalPath = new Path<Airport, FlightSegment, Schedule>();
                    if (spurPath.Edges.Count > 0)
                    {
                        totalPath.Edges.AddRange(rootPath.Edges);
                        totalPath.Edges.AddRange(spurPath.Edges);
                        totalPath.Cost = rootPath.Cost + spurPath.Cost;
                        B.Add(totalPath);
                    }
                }
                B.Sort();
                if (B.Count == 0) break;
                A.Add(B[0]);
                B.RemoveAt(0);
                graph = graphCopy;
            }
            return A;
        }
    }
}
